1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| #include <cstdio>
#include <algorithm>
#define LL long long
const int maxn = 1505;
using namespace std;
LL s[maxn][maxn], a[4][maxn][maxn], f[maxn][maxn], x[maxn][maxn];
int n, m, k;
int main(){
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
scanf("%lld", x[i] + j);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + x[i][j];
for (int i = k; i <= n; i++)
for (int j = k; j <= m; j++)
f[i][j] = s[i][j] - s[i - k][j] - s[i][j - k] + s[i - k][j - k];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
a[0][i][j] = max(max(a[0][i - 1][j], a[0][i][j - 1]), f[i][j]);
for (int i = n; i >= 1; i--)
for (int j = 1; j <= m; j++)
a[1][i][j] = max(max(a[1][i + 1][j], a[1][i][j - 1]), f[i + k - 1][j]);
for (int i = 1; i <= n; i++)
for (int j = m; j >= 1; j--)
a[2][i][j] = max(max(a[2][i - 1][j], a[2][i][j + 1]), f[i][j + k - 1]);
for (int i = n; i >= 1; i--)
for (int j = m; j >= 1; j--)
a[3][i][j] = max(max(a[3][i + 1][j], a[3][i][j + 1]), f[i + k - 1][j + k - 1]);
LL ans = 0;
for (int i = k; i <= n - k + 1; i++)
for (int j = k; j <= m - k + 1; j++)
ans = max(ans, a[0][i][j] + a[1][i + 1][j] + a[2][n][j + 1]);
for (int i = k; i <= n - k + 1; i++)
for (int j = k; j <= m - k + 1; j++)
ans = max(ans, a[0][n][j] + a[2][i][j + 1] + a[3][i + 1][j + 1]);
for (int i = k; i <= n - k + 1; i++)
for (int j = k; j <= m - k + 1; j++)
ans = max(ans, a[1][i + 1][j] + a[3][i + 1][j + 1] + a[0][i][m]);
for (int i = k; i <= n - k + 1; i++)
for (int j = k; j <= m - k + 1; j++)
ans = max(ans, a[0][i][j] + a[2][i][j + 1] + a[3][i + 1][1]);
for (int i = k; i <= n; i++)
for (int j = k; j <= m - k + 1; j++)
ans = max(ans, a[0][n][j - k] + a[2][n][j + 1] + f[i][j]);
for (int i = k; i <= n - k + 1; i++)
for (int j = k; j <= m; j++)
ans = max(ans, a[0][i - k][m] + a[3][i + 1][1] + f[i][j]);
printf("%lld\n", ans);
return 0;
}
|